package leetcode.editor.cn;
//2021-08-25 13:10:46	获取当前时间
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "()[]{}"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：s = "(]"
//输出：false
// 
//
// 示例 4： 
//
// 
//输入：s = "([)]"
//输出：false
// 
//
// 示例 5： 
//
// 
//输入：s = "{[]}"
//输出：true 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 仅由括号 '()[]{}' 组成 
// 
// Related Topics 栈 字符串 
// 👍 2592 👎 0


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution_有效的括号 {
    public static void main(String[] args) {
        Solution_有效的括号 solution = new Solution_有效的括号();
        boolean valid = solution.isValid("(([]){})");
        System.out.println("valid = " + valid);
    }
    public boolean isValid(String s) {
        //把字符串切割成字符数组
        //遍历数组，存储字符为'(' '{' '['的三类字符，直到有')' '}' ']'中的一类出现则停止存储字符，
        // 并且按照先进后出的原则取出之前存储的字符，依次和接下来的字符比较，看是否是相对应的括号，直到存储的字符比较完，在这之前有'(' '{' '[' 任何一类出现，则判定位false，
        //如果比较完后面还有字符循环上面步骤，直到字符数组遍历完，如果全部匹配则返回true

        //定义存储'(' '{' '[' 这三类括号的list
        LinkedList<String> list = new LinkedList();
        boolean flag = true;
        //定义括号的正确对应映射
        Map map = new HashMap();
        map.put("(", ")");
        map.put("{", "}");
        map.put("[","]");
        //遍历字符数组
        for (String s1 : s.split("")) {
            if (map.keySet().contains(s1)) {
                list.addLast(s1);
            } else {
                if (list.size() == 0) {
                    return false;
                }
                if (s1.equals(map.get(list.removeLast()))) {
                    if (list.size() == 0) {
//                        flag = true;
                    }
                    continue;
                } else {
                    return false;
                }
            }
        }
        if(list.size() != 0) {
            return false;
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
